'''
https://leetcode.cn/problems/missing-element-in-sorted-array
'''
from typing import List


class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        l, r = nums[0], nums[-1]
        i = 0
        while l <= r:
            if l == nums[i]:
                i += 1
                l += 1
            else:
                k -= 1
                if k == 0:
                    return l
                l += 1
        return r + k

    def missingElement2(self, nums: List[int], k: int) -> int:
        def f(t):
            return nums[t] - nums[0] - (t - 0)

        n = len(nums)
        l, r = 0, n - 1
        res = n - 1
        while l <= r:
            m = l + r >> 1
            if f(m) >= k:
                res = m
                r = m - 1
            else:
                l = m + 1

        n_missing = f(res)
        # print(res, n_missing)
        # print(nums[res] - (n_missing - k) - 1)
        return nums[res] - (n_missing - k) - 1 if k <= n_missing else nums[res] + k - n_missing


nums = [4, 7, 9, 10]
k = 1
print(Solution().missingElement2(nums, k))
